{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. Median of Two Sorted Arrays**  <font color=red size=3>_hard_</font>\n",
    "\n",
    "There are two sorted arrays nums1 and nums2 of size m and n respectively.  \n",
    "Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).  \n",
    "You may assume nums1 and nums2 cannot be both empty.\n",
    "\n",
    "**Example 1**\n",
    "\n",
    "```\n",
    "nums1 = [1, 3]  \n",
    "nums2 = [2]  \n",
    "\n",
    "The median is 2.0\n",
    "```\n",
    "\n",
    "**Example 2**\n",
    "\n",
    "```\n",
    "nums1 = [1, 2]\n",
    "nums2 = [3, 4]\n",
    "\n",
    "The median is (2 + 3)/2 = 2.5 \n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n",
      "5\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# def findMedianSortedArrays(nums1, nums2):\n",
    "#     \"\"\"\n",
    "#     :type nums1: List[int]\n",
    "#     :type nums2: List[int]\n",
    "#     :rtype: float\n",
    "#     \"\"\"\n",
    "#     len1 = len(nums1)\n",
    "#     len2 = len(nums2)\n",
    "#     total_lengh = len1 + len2\n",
    "#\n",
    "#     i = 0\n",
    "#     j = 0\n",
    "#     res = []\n",
    "#     while i < len1 and j < len2:\n",
    "#         if nums1[i] > nums2[j]:\n",
    "#             res.append(nums2[j])\n",
    "#             j += 1\n",
    "#         else:\n",
    "#             res.append(nums1[i])\n",
    "#             i += 1\n",
    "#     if i < len1 - 1:\n",
    "#         res.append(nums1[i+1:])\n",
    "#     elif j < len2 - 1:\n",
    "#         res.append(nums2[j+1:])\n",
    "#\n",
    "#     if total_lengh % 2 == 0:\n",
    "#         median_index = total_lengh / 2\n",
    "#     else:\n",
    "#         median_index = total_lengh // 2 + 1\n",
    "#     # print median_index\n",
    "#     if total_lengh % 2 == 0:\n",
    "#         return (res[median_index - 1] + res[median_index]) /2\n",
    "#     else:\n",
    "#         return res[median_index - 1]\n",
    "\n",
    "def median(A, B):\n",
    "    m, n = len(A), len(B)\n",
    "    if m > n:\n",
    "        A, B, m, n = B, A, n, m\n",
    "    if n == 0:\n",
    "        raise ValueError\n",
    "\n",
    "    imin, imax, half_len = 0, m, (m + n + 1) // 2\n",
    "    while imin <= imax:\n",
    "        i = (imin + imax) // 2\n",
    "        j = half_len - i\n",
    "        if i < m and B[j-1] > A[i]:\n",
    "            # i is too small, must increase it\n",
    "            imin = i + 1\n",
    "        elif i > 0 and A[i-1] > B[j]:\n",
    "            # i is too big, must decrease it\n",
    "            imax = i - 1\n",
    "        else:\n",
    "            # i is perfect\n",
    "\n",
    "            if i == 0: max_of_left = B[j-1]\n",
    "            elif j == 0: max_of_left = A[i-1]\n",
    "            else: max_of_left = max(A[i-1], B[j-1])\n",
    "\n",
    "            if (m + n) % 2 == 1:\n",
    "                return max_of_left\n",
    "\n",
    "            if i == m: min_of_right = B[j]\n",
    "            elif j == n: min_of_right = A[i]\n",
    "            else: min_of_right = min(A[i], B[j])\n",
    "\n",
    "            return (max_of_left + min_of_right) // 2\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums1 = [1,3]\n",
    "    nums2 = [2]\n",
    "    print(median(nums1, nums2))\n",
    "\n",
    "    nums1 = [1, 3, 8, 12]\n",
    "    nums2 = [0, 1, 5, 7, 11]\n",
    "    print(median(nums1, nums2))\n",
    "\n",
    "    nums1 = [1, 3, 5, 12, 13]\n",
    "    nums2 = [0, 1, 8, 7]\n",
    "    print(median(nums1, nums2))\n",
    "\n",
    "    nums1 = [1, 3, 5, 12]\n",
    "    nums2 = [0, 1, 8, 7]\n",
    "    print(median(nums1, nums2))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
